#include <iostream>
#define M 2 //阶树都为双 M=2 4阶b树

using namespace std;

int btree_node_num = 0;


typedef struct btree_node
{
    int k[2 * M - 1];            //数据 key
    struct btree_node *p[2 * M]; //指针
    bool is_leaf;
    int num;
} btree_node;
btree_node *btree_delete(btree_node *, int);

btree_node *btree_node_new()
{
    btree_node *node = (btree_node *)malloc(sizeof(btree_node));
    if (NULL == node)
        return NULL;
    for (int i = 0; i < 2 * M - 1; ++i)
    {
        node->k[i] = 0;
    }
    for (int i = 0; i < 2 * M; ++i)
    {
        node->p[i] = NULL;
    }
    node->num = 0;
    node->is_leaf = true;
    return node;
}

btree_node *btree_create()
{
    btree_node *node = btree_node_new();
    if (NULL == node)
    {
        return NULL;
    }
    return node;
}

int btree_split_child(btree_node *parent, int pos, btree_node *child)
{
    btree_node *new_child = btree_node_new();
    if (NULL == new_child)
    {
        return -1;
    }
    new_child->is_leaf = child->is_leaf;
    new_child->num = M - 1;

    for (int i = 0; i < M - 1; ++i)
    {
        new_child->k[i] = child->k[i + M];
    }

    if (false == new_child->is_leaf)
    {
        for (int i = 0; i < M; ++i)
        {
            new_child->p[i] = child->p[i + M];
        }
    }
    child->num = M - 1;

    for (int i = parent->num; i > pos; --i)
    {
        parent->p[i + 1] = parent->p[i];
    }
    parent->p[pos + 1] = new_child;
    for (int i = parent->num - 1; i >= pos; --i)
    {
        parent->k[i + 1] = parent->k[i];
    }
    parent->k[pos] = child->k[M - 1];
    parent->num += 1;

    return 0;
}

void btree_insert_nonfull(btree_node *node, int target)
{
    if (node->is_leaf)
    {
        int pos = node->num;
        while (pos >= 1 && target < node->k[pos - 1])
        {
            node->k[pos] = node->k[pos - 1];
            --pos;
        }
        node->k[pos] = target;
        node->num += 1;
        ++btree_node_num;
    }
    else
    {
        int pos = node->num;
        while (pos > 0 && target < node->k[pos - 1])
        {
            --pos;
        }

        if (2 * M - 1 == node->p[pos]->num)
        {
            btree_split_child(node, pos, node->p[pos]);
            if (target > node->k[pos])
            {
                ++pos;
            }
        }
        btree_insert_nonfull(node->p[pos], target);
    }
}

btree_node *btree_insert(btree_node *root, int target)
{
    if (NULL == root)
    {
        return NULL;
    }

    if (2 * M - 1 == root->num)
    {
        btree_node *node = btree_node_new();
        if (NULL == node)
        {
            return root;
        }

        node->is_leaf = false;
        node->p[0] = root;
        btree_split_child(node, 0, root);
        btree_insert_nonfull(node, target);
        return node;
    }
    else
    {
        btree_insert_nonfull(root, target);
        return root;
    }
}

void btree_merge_child(btree_node *root, int pos, btree_node *y, btree_node *z)
{
    y->num = 2 * M - 1;
    for (int i = M; i < 2 * M - 1; ++i)
    {
        y->k[i] = z->k[i - M];
    }
    y->k[M - 1] = root->k[pos];

    if (false == z->is_leaf)
    {
        for (int i = M; i < 2 * M; ++i)
        {
            y->p[i] = z->p[i - M];
        }
    }

    for (int j = pos + 1; j < root->num; ++j)
    {
        root->k[j - 1] = root->k[j];
        root->p[j] = root->p[j + 1];
    }
    --root->num;
    free(z);
}

int btree_search_predecessor(btree_node *root)
{
    btree_node *y = root;
    while (!y->is_leaf)
    {
        y = y->p[y->num];
    }
    return y->k[y->num - 1];
}
int btree_search_successor(btree_node *root)
{
    btree_node *z = root;
    while (!z->is_leaf)
    {
        z = z->p[0];
    }
    return z->k[0];
}

void btree_shift_to_right_child(btree_node *root, int pos, btree_node *y, btree_node *z)
{
    ++z->num;
    for (int i = z->num - 1; i > 0; --i)
    {
        z->k[i] = z->k[i - 1];
    }
    z->k[0] = root->k[pos];
    root->k[pos] = y->k[y->num - 1];

    if (false == z->is_leaf)
    {
        for (int i = z->num; i > 0; --i)
        {
            z->p[i] = z->p[i - 1];
        }
        z->p[0] = y->p[y->num];
    }
    --y->num;
}
void btree_shift_to_left_child(btree_node *root, int pos, btree_node *y, btree_node *z)
{
    ++y->num;
    y->k[y->num - 1] = root->k[pos];
    root->k[pos] = z->k[0];

    for (int j = 1; j < z->num; ++j)
    {
        z->k[j - 1] = z->k[j];
    }

    if (false == z->is_leaf)
    {
        y->p[y->num] = z->p[0];
        for (int j = 1; j <= z->num; ++j)
        {
            z->p[j - 1] = z->p[j];
        }
    }
    --z->num;
}

void btree_delete_nonone(btree_node *root, int target)
{
    if (true == root->is_leaf)
    {
        int i = 0;
        while (i < root->num && target > root->k[i])
        {
            ++i;
        }
        if (target == root->k[i])
        {
            for (int j = i + 1; j < 2 * M - 1; ++j)
            {
                root->k[j - 1] = root->k[j];
            }
            --root->num;
            --btree_node_num;
        }
        else
        {
            cout << "target not found" << endl;
        }
    }
    else
    {
        int i = 0;
        btree_node *y = NULL, *z = NULL;
        while (i < root->num && target > root->k[i])
        {
            ++i;
        }
        if (i < root->num && target == root->k[i])
        {
            y = root->p[i];
            z = root->p[i + 1];
            if (y->num > M - 1)
            {
                int pre = btree_search_predecessor(y);
                root->k[i] = pre;
                btree_delete_nonone(y, pre);
            }
            else if (z->num > M - 1)
            {
                int next = btree_search_successor(z);
                root->k[i] = next;
                btree_delete_nonone(z, next);
            }
            else
            {
                btree_merge_child(root, i, y, z);
                btree_delete(y, target);
            }
        }
        else
        {
            y = root->p[i];
            if (i < root->num)
            {
                z = root->p[i + 1];
            }
            btree_node *p = NULL;
            if (i > 0)
            {
                p = root->p[i - 1];
            }
            if (y->num == M - 1)
            {
                if (i > 0 && p->num > M - 1)
                {
                    btree_shift_to_right_child(root, i - 1, p, y);
                }
                else if (i < root->num && z->num > M - 1)
                {
                    btree_shift_to_left_child(root, i, y, z);
                }
                else if (i > 0)
                {
                    btree_merge_child(root, i - 1, p, y);
                    y = p;
                }
                else
                {
                    btree_merge_child(root, i, y, z);
                }
                btree_delete_nonone(y, target);
            }
            else
            {
                btree_delete_nonone(y, target);
            }
        }
    }
}

btree_node *btree_delete(btree_node *root, int target)
{
    if (1 == root->num)
    {
        btree_node *y = root->p[0];
        btree_node *z = root->p[1];
        if (NULL != y && NULL != z && M - 1 == y->num && M - 1 == z->num)
        {
            btree_merge_child(root, 0, y, z);
            free(root);
            btree_delete_nonone(y, target);
            return y;
        }
        else
        {
            btree_delete_nonone(root, target);
            return root;
        }
    }
    else
    {
        btree_delete_nonone(root, target);
        return root;
    }
}

//--------------------------------------------

/*
void btree_inorder_print(btree_node *root)
{
    if (NULL != root)
    {
        btree_inorder_print(root->p[0]);
        for (int i = 0; i < root->num; ++i)
        {
            cout << root->k[i] << " ";
            btree_inorder_print(root->p[i+1]);
        }
    }
}

void btree_level_display(btree_node *root)
{
    btree_node *queue[200] = {NULL};
    int front = 0;
    int rear = 0;
    queue[rear++] = root;
    while (front < rear)
    {
        btree_node *node = queue[front++];
        cout << "[";
        for (int i = 0; i < node->num; ++i)
        {
            cout << node->k[i] << " ";
        }
        cout << "]";

        for (int i = 0; i <= node->num; ++i)
        {
            if (NULL != node->p[i])
            {
                queue[rear++] = node->p[i];
            }
        }
    }
    cout << endl;
}

int main() {
    int a[] = {8,3,2,10,9,1,4};

    btree_node *root = btree_create();
    for (int i = 0; i < sizeof(a)/sizeof(int); ++i) {
        root = btree_insert(root, a[i]);
    }
    btree_level_display(root);
    
    root = btree_delete(root, 10);
    btree_level_display(root);
}
*/